1428. Leftmost Column with at Least a One
Medium

(This problem is an interactive problem.)

A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return the index (0-indexed) of the leftmost column with a 1 in it. If such an index does not exist, return -1.

You can't access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

  • BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed).
  • BinaryMatrix.dimensions() returns the dimensions of the matrix as a list of 2 elements [rows, cols], which means the matrix is rows x cols.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes, the input will be the entire binary matrix mat. You will not have access to the binary matrix directly.

 

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

 

Constraints:

  • rows == mat.length
  • cols == mat[i].length
  • 1 <= rows, cols <= 100
  • mat[i][j] is either 0 or 1.
  • mat[i] is sorted in non-decreasing order.
Accepted
99,628
Submissions
199,011
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
1. (Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.
Show Hint 2
2. (Optimal Approach) Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down. If the value at p is 0, move down. If the value at p is 1, move left. Try to figure out the correctness and time complexity of this algorithm.

Average Rating: 4.96 (73 votes)

Premium

Solution


Approach 1: Linear Search Each Row

Intuition

This approach won't pass, but we'll use it as a starting point. Also, it might be helpful to you if you just needed an example of how to use the API, but don't want to see a complete solution yet!

The leftmost 1 is the 1 with the lowest column index.

The problem can be broken down into finding the index of the first 1 in each row and then taking the minimum of those indexes.

Diagram showing a linear search that has uncovered all the zeroes, along with the first 1 in each row.

The simplest way of doing this would be a linear search on each row.

Algorithm

Complexity Analysis

If you ran this code, you would have gotten the following error.

You made too many calls to BinaryMatrix.get().

The maximum grid size is 100 by 100, so it would contain 10000 cells. In the worst case, the linear search algorithm we implemented has to check every cell. With the problem description telling us that we can only make up to 1000 API calls, this clearly isn't going to work.

Let NN be the number of rows, and MM be the number of columns.

  • Time complexity : O(NM)O(N \cdot M)

    We don't know the time complexity of binaryMatrix.get() as its implementation isn't our concern. Therefore, we can assume it's O(1)O(1).

    In the worst case, we are retrieving a value for each of the NMN \cdot M cells. At O(1)O(1) per operation, this gives a total of O(NM)O(N \cdot M).

  • Space complexity : O(1)O(1).

    We are only using constant extra space.



Approach 2: Binary Search Each Row

Intuition

This isn't the best approach, but it passes, and coding it up is a good opportunity to practice binary search.

When linear search is too slow, we should try to find a way to use binary search. If you're not familiar with binary search, check out this Explore Card!. We recommend doing the first couple of binary search questions to get familiar with the algorithm before coming back to this problem.

Also, have a go at First Bad Version. The only difference between that problem and this one is that instead of 0 and 1, it uses false and true.

Like we did with the linear search, we're going to apply binary search independently on each row. The target element we're searching for is the first 1 in the row.

The core part of a binary search algorithm is how it decides whether the target element is to the left or the right of the middle element. Let's figure this out by thinking through a couple of examples.

In the row below, we've determined that the middle element is a 0. On what side must the target element (first 1) be? The left, or the right? Don't forget, all the 0's are before all the 1's.

Diagram showing a single uncovered 0 at the "middle" index

In this next row, the middle element is a 1? What side must the target element be on? Could it also possibly be the 1 we just found?

Diagram showing a single uncovered 1 at the "middle" index

For the first example, we can conclude that the target element (if it exists) must be to the right of the middle element. This is because we know that everything to the left of a 0 must also be a 0,

For the second example, we can conclude that the target element is either the middle element itself or it is some other 1 to the left of the middle element. We know that everything to the right of a 1 is also a 1, but these can't possibly be further left than the one we just found.

In summary, if the middle element is a:

  • 0, then the target must be to the right.
  • 1, then the target is either this element or to the left.

We can then put this together into an algorithm that finds the index of the target element (first 1) in each row, and then returns the minimum of those indexes. Here is an animation of how that algorithm would look. The light grey numbers are the ones that we could infer without needing to make an API call. They are only there to help you understand.

Current
1 / 33

Algorithm

If you're already quite familiar with binary search, feel free to skip down to the implementation below. I've decided to include lots of details here, as binary search is one of those algorithms that a lot of people get frustrated with easily and find it difficult to master.

In a binary search, we always keep track of the range that the target might be in by using two variables: lo to represent the lowest possible index it could be, and hi to represent the highest possible index it could be. Ignoring the binaryMatrix API details for the moment, here is a rough outline of our binary search in pseudocode.

define function binary_search(input_list):
    lo = the lowest possible index
    hi = the highest possible index
    while the search space contains 2 or more items:
        mid = the middle index in the remaining search space
        if the element at input_list[mid] is 0:
            lo = mid + 1 (the first 1 is *further right*, and can't be mid itself)
        else:
            hi = mid (the first 1 is either mid itself, *or is further left*)
    return the only index remaining in the search space

As always in binary search, there are a couple more key implementation details we still need to deal with:

  1. An even-length search space has two middles. Which do we choose?
  2. The row might be all 0's.

Let's tackle these issues one at a time.

The first issue, the choice of middle, is important, as otherwise, the search space might stop shrinking when it gets down to two elements. When the search space doesn't shrink, the algorithm does the exact same thing the next loop cycle, resulting in an infinite loop. Remember that when the search space only contains two elements, they are the ones pointed to by lo and hi. This means that the lower middle equals lo, and the upper-middle equals hi. We, therefore, need to think about which cases would shrink the search space, and which would not.

If we use the lower-middle

  • If it is a 0, then we set lo = mid + 1. Because hi == mid + 1, this means that lo == hi (search space is of length-one).
  • If it is a 1, then we set hi = mid. Because mid == lo, this means that hi == lo (search space is of length-one).

If we use the upper-middle

  • If it is a 0, then we set lo = mid + 1. Because hi = mid, we now have hi > lo (search space is of length-zero).
  • If it is a 1, then we set hi = mid. Because hi == mid was already true, the search space stays as is (of length-two).

If we use the lower-middle, we know the search space will always shrink. If we use the upper-middle, it might not. Therefore, we should go with the lower-middle. The formula for this is mid = (low + high) / 2.

The second issue, a row of all zeroes, is solved by recognizing that the algorithm always shrinks down the search space to a single element. This is supposed to be the first 1, but if that doesn't exist, then it has to be a 0. Therefore, we can detect this case by checking whether or not the last element in the search space is a 1.

It is good practice to think these details through carefully so that you can write your binary search algorithm decisively and confidently. Resist the urge to Program by Permutation!

Anyway, putting this all together, we get the following code.

Complexity Analysis

Let NN be the number of rows, and MM be the number of columns.

  • Time complexity : O(NlogM)O(N \, \log \, M).

    There are MM items in each row. Therefore, each binary search will have a cost of O(logM)O(\log \, M). We are performing NN of these binary searches, giving a time complexity of NO(logM)=O(NlogM)N \cdot O(\log \, M) = O(N \, \log \, M).

  • Space complexity : O(1)O(1).

    We are using constant extra space.



Approach 3: Start at Top Right, Move Only Left and Down

Intuition

Did you notice in Approach 2 that we didn't need to finish searching all the rows? One example of this was row 3 on the example in the animation. At the point shown in the image below, it was clear that row 3 could not possibly be better than the minimum we'd found so far.

Diagram showing redundant search in Row 3

Therefore, an optimization we could have made was to keep track of the minimum index so far, and then abort the search on any rows where we have discovered a 0 at, or to the right of, that minimum index.

We can do even better than that; on each search, we can set hi = smallest_index - 1, where smallest_index is the smallest index of a 1 we've seen so far. In most cases, this is a substantial improvement. It works because we're only interested in finding 1s at lower indexes than we previously found. Here is an animation of the above example with this optimized algorithm. The algorithm eliminates as many cells as it can with each API call. It also starts by checking the last cell of the row before proceeding with the binary search, to eliminate needless binary searches where the row only had 0s left in it.

Current
1 / 17

Here is what the worst-case looks like. Like before, its time complexity is still O(MlogN)O(M \, \log \, N).

The worst case for the optimized algorithm

While this is no worse than Approach 2, there is a better algorithm.

Start in the top right corner, and if the current value is a 0, move down. If it is a 1, then move left.

The easiest way to see why this works is an example. Here is an animation of it.

Current
1 / 17

You probably gained some intuitive sense as to why this works, just from watching the animation.

  • When we encounter a 0, we know that the leftmost 1 can't be to the left of it.
  • When we encounter a 1, we should continue the search on that row (move pointer to the left), in order to find an even smaller index.

Algorithm

Complexity Analysis

Let NN be the number of rows, and MM be the number of columns.

  • Time complexity : O(N+M)O(N + M).

    At each step, we're moving 1 step left or 1 step down. Therefore, we'll always finish looking at either one of the MM rows or NN columns. Therefore, we'll stay in the grid for at most N+MN + M steps, and therefore get a time complexity of O(N+M)O(N + M).

  • Space complexity : O(1)O(1).

    We are using constant extra space.


Report Article Issue

Comments: 38
NegativeIndex's avatar
Read More

O(M+N) can be worse than O(NlogM) if M is much large than N.

62
Show 6 replies
Reply
Share
Report
hisenberg10's avatar
Read More

One of the optimization that I thought of when I saw the problem was the fact that each row is sorted (or is non-decreasing). So we can prune candidate rows just by looking at the last column of each row. If the last column is 1, then that means, we can binary search this row, on the other hand, if the last row is 0, then there is no point in searching this row.

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        
        rows, cols = binaryMatrix.dimensions()
        min_col = float("inf")
        
        def get_left_most(row_id: int) -> int: # returns the earliest 1
            start, end = 0, cols
            
            while start < end:
                mid = start + (end-start)//2
                if binaryMatrix.get(row_id, mid) == 1:
                    end = mid
                else:
                    if mid > min_col:
                        return float("inf") # no point in searching to the 
                                            # right of already low soln
                    start = mid + 1
                    
            return start
        
        for i in range(rows):
            if binaryMatrix.get(i, cols-1) == 1: # candidate row
                first_1 = get_left_most(i)
                min_col = min(min_col, first_1)
        
        return min_col if min_col != inf else -1

9
Show 2 replies
Reply
Share
Report
Minibar's avatar
Read More

This is one of the best binary search space explanations.

6
Reply
Share
Report
sergiitk's avatar
Read More

Python 3 code to illustrate the first part of the Approach 3, complexity O(MlogN).
Bisect left each row up to the current best answer.

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        mat = binaryMatrix
        R, C = mat.dimensions()
        ans = C
        for r in range(R):
            idx = self.bisect_left(mat, r, ans)
            ans = min(ans, idx)
        
        return -1 if ans == C else ans

    def bisect_left(self, mat, r, hi):
        lo = 0
        while lo < hi:
            mi = lo + (hi-lo)//2
            if mat.get(r, mi):
                hi = mi
            else:
                lo = mi + 1
        
        return hi

5
Show 2 replies
Reply
Share
Report
chethanrao's avatar
Read More

As mentioned before guess we can combine approach 2 and 3 for better results!

7
Show 3 replies
Reply
Share
Report
KickStartInterview's avatar
Read More

why do they use the word "non-decreasing order." they can just say increasing order... Am I missing something here?

4
Show 1 reply
Reply
Share
Report
flash_solve's avatar
Read More

We don't have to binary Search for entire row. We can keep track of where we found the 1 in the above row, and that can be used as right boundary for next row.

3
Show 1 reply
Reply
Share
Report
dbalagula's avatar
Read More

binary search can be greatly optimized. You can check if low is greater or equal to your currently found smallest index. If that's the case, you can break out of the binary search for that row since any index it may possibly return cannot be less than what you've already seen

from math import inf

# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
#class BinaryMatrix(object):
#    def get(self, row: int, col: int) -> int:
#    def dimensions(self) -> list[]:

class Solution:
    
    def searchRow(self, matrix, row_index, row_len, min_found):
        low = 0
        high = row_len - 1
        while low <= high and low < min_found:
            mid = (low + high) // 2
            if matrix.get(row_index, mid) == 0:
                low = mid + 1
            else:
                min_found = min(min_found, mid)
                high = mid - 1
        return min_found
    
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        num_rows, num_cols = binaryMatrix.dimensions()
        min_found = inf
        for i in range(num_rows):
            min_found = min(min_found, self.searchRow(binaryMatrix, i, num_cols, min_found))
        if min_found == inf:
            return -1
        return min_found

3
Reply
Share
Report
sobolxxx's avatar
Read More

So are the columns sorted? Is this matrix proper?
[ 1 1 ]
[ 0 1 ]
?
Either the description of the problem is wrong, or the solution is wrong - solution assumes both rows and columns are sorted. Description explains that only rows are sorted.

1
Show 2 replies
Reply
Share
Report
small_deer's avatar
Read More

We can combine solution 2 and solution 3: every time we go down to the next row, we use binary search to find the target 1 instead of a trivial linear search

1
Show 1 reply
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.